package com.demo.java.OD101_150.OD140;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【合并数组】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145732384
 */
public class OdMain {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            int len = Integer.parseInt(s.nextLine());  // 获取每个数组的长度
            int num = Integer.parseInt(s.nextLine());  // 获取数组的数量
            String[] arrays = new String[num];  // 存储每个数组的字符串
            for (int i = 0; i < num; ++i) {
                arrays[i] = s.nextLine();  // 读取每个数组
            }
            solveMethod(len, arrays);  // 调用解题方法
        }
    }

    private static void solveMethod(int len, String[] arrays) {
        // 创建最小堆
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        // 用来存储最终合并后的结果
        List<String> res = new ArrayList<>();
        // 计算合并后的数组总长度
        int sum = 0;

        // 初始化最小堆，将每个数组的第一个元素加入堆中
        for (int i = 0; i < arrays.length; i++) {
            String[] arr = arrays[i].split(",");  // 按逗号分隔字符串
            sum += arr.length;  // 累计总元素数
            if (arr.length > 0) {
                pq.offer(new Pair(arr[0], i, 0));  // 将第一个元素放入堆
            }
        }

        // 从最小堆中取出元素，直到结果数组中包含所有元素
        while (res.size() != sum) {
            Pair p = pq.poll();  // 获取最小元素
            res.add(p.s);  // 将该元素添加到结果中
            int i = p.i;  // 当前元素所在的数组索引
            int j = p.j + 1;  // 当前元素的下一个位置
            // 如果该数组还有元素，继续将下一个元素加入堆
            if (j < arrays[i].split(",").length) {
                pq.offer(new Pair(arrays[i].split(",")[j], i, j));
            }
        }

        // 输出合并后的数组
        System.out.println(String.join(",", res));
    }

    // 定义一个Pair类，存储每个元素、数组索引和元素索引
    static class Pair implements Comparable<Pair> {
        String s;
        int i;
        int j;

        public Pair(String s, int i, int j) {
            this.s = s;
            this.i = i;
            this.j = j;
        }

        // 按照字典顺序比较元素
        @Override
        public int compareTo(Pair o) {
            return s.compareTo(o.s);
        }
    }
}